class Solution:
    def canCompleteCircuit(self, gas, cost) -> int:
        reward = [gas[x] - cost[x] for x in range(len(gas))]
        gas_len = len(gas)
        print(reward)
        start = -1
        for i in range(len(reward)):
            if reward[i] >= 0:
                start = i
                break
        if start == -1:
            return -1
        end = (start + 1) % gas_len
        rest = reward[start]
        while end != start:
            rest += reward[end]
            end = (end + 1) % gas_len
            if rest >= 0:
                continue
            # 剩余油量小于0，start往回移动，直到积累油量足够补充损耗
            while rest < 0:
                start = (start - 1 + gas_len) % gas_len
                if end == (start + 1) % gas_len:
                    return -1
                rest += reward[start]

        return start if end == start else -1


if __name__ == '__main__':
    so = Solution()
    gas = [5, 1, 2, 3, 4]
    cost = [4, 4, 1, 5, 1]
    # gas = [5, 8, 2, 8]
    # cost = [6, 5, 6, 6]
    re = so.canCompleteCircuit(gas, cost)
    print(re)
